package com.heima.leetcode.practice;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 494. 目标和
 * @date 2025/2/17 12:14
 */
public class E494 {

    /**
     * 达到目标和的方法数
     */
    private int count = 0;

    /**
     * <h3>方法一：dfs，时间复杂度O(2^N)，效率慢</h3>
     * @param nums nums
     * @param target target
     * @return 得到目标和的方法数
     */
    public int findTargetSumWays1(int[] nums, int target) {
        dfs(nums, target, 0, 0);
        return count;
    }

    /**
     * dfs，每次选一个加法或者减法，类比于二项式展开
     * @param nums nums
     * @param target 目标和
     * @param index 当前索引
     * @param sum 当前和
     */
    private void dfs(int[] nums, int target, int index, int sum) {
        if (index == nums.length){
            if (sum == target) count++;
            return;
        }
        dfs(nums, target, index + 1, sum + nums[index]);
        dfs(nums, target, index + 1, sum - nums[index]);
    }

    // 分成任意可能的两个子集：P N，可转化为sum(P) - sum(N) = target的情况总数
    // 假设全集为S，那么sum(P) - (sum(S) - sum(P)) = target
    // => sum(P) = (sum(S) + target)/2
    // 问题就转化为了和为(sum(S) + target)/2的子集数
    // 就考虑用动态规划，dp[i][j] 表示前i个数中，和为j的子集数

    /**
     * <h3>方法二：动态规划，时间复杂度O(N*S)，效率快</h3>
     * @param nums nums数组
     * @param target 目标和
     * @return 得到目标和的方法数
     */
    public int findTargetSumWays2(int[] nums, int target) {
        int sum = 0, newTarget = 0;
        for (int num : nums) sum += num;
        if (((target + sum) & 1) != 0 || Math.abs(target) > sum) return 0;
        newTarget = (target + sum) >> 1;
        int[][] dp = new int[nums.length + 1][newTarget + 1];
        dp[0][0] = 1; // 空集的和为 0
        for (int i = 1; i <= nums.length; i++) {
            for (int j = 0; j <= newTarget; j++) {
                if (j >= nums[i - 1]) {
                    // 当前元素可以选择加入子集，前面i-1个元素中，和为j或者j-nums[i-1]的子集数
                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i - 1]];
                } else {
                    // 当前元素不能加入子集
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[nums.length][newTarget];
    }
}
